package com.tgy.algorithm._经典题目01;

import java.util.Arrays;

/**
 * 给定一个正整数M，请构造出一个长度为M的数组arr，
 * 要求对任意的i、j、k三个位置，如果i<j<k，都有arr[i] + arr[k] != 2*arr[j]
 * 返回构造出的arr
 */
public class _006_构造任意的i加j不等于2k {

    public static int[] doubleArr(int k) {

        if (k <= 1) {
            return new int[]{1};
        }

        // 2  1
        // 7  4 四个数
        // 6  3
        // 8 4
        int len = (k + 1) >> 1;
        int[] ints = doubleArr(len);
        int[] rets = new int[k];
        for (int i = 0; i < len; i++) {
            rets[i] = (ints[i] << 1) - 1;
        }

        for (int i = len; i < k ; i++) {
            rets[i] = (ints[i - len] << 1);
        }

        return rets;
    }

    public static void main(String[] args) {
        int[] nums = doubleArr(10);
        System.out.println(Arrays.toString(nums));
    }
}
